1   /*
2    * Copyright (C) 2011 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.math;
18  
19  import static com.google.common.math.MathPreconditions.checkNonNegative;
20  import static java.lang.Math.log;
21  
22  import com.google.common.annotations.GwtCompatible;
23  import com.google.common.annotations.VisibleForTesting;
24  import com.google.common.primitives.Booleans;
25  
26  /**
27   * A class for arithmetic on doubles that is not covered by {@link java.lang.Math}.
28   *
29   * @author Louis Wasserman
30   * @since 11.0
31   */
32  @GwtCompatible(emulated = true)
33  public final class DoubleMath {
34    /*
35     * This method returns a value y such that rounding y DOWN (towards zero) gives the same result
36     * as rounding x according to the specified mode.
37     */
38  
39    private static final double MIN_INT_AS_DOUBLE = -0x1p31;
40    private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0;
41  
42    private static final double MIN_LONG_AS_DOUBLE = -0x1p63;
43    /*
44     * We cannot store Long.MAX_VALUE as a double without losing precision.  Instead, we store
45     * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1.
46     */
47    private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63;
48  
49    /**
50     * Returns the base 2 logarithm of a double value.
51     *
52     * <p>Special cases:
53     * <ul>
54     * <li>If {@code x} is NaN or less than zero, the result is NaN.
55     * <li>If {@code x} is positive infinity, the result is positive infinity.
56     * <li>If {@code x} is positive or negative zero, the result is negative infinity.
57     * </ul>
58     *
59     * <p>The computed result is within 1 ulp of the exact result.
60     *
61     * <p>If the result of this method will be immediately rounded to an {@code int},
62     * {@link #log2(double, RoundingMode)} is faster.
63     */
64    public static double log2(double x) {
65      return log(x) / LN_2; // surprisingly within 1 ulp according to tests
66    }
67  
68    private static final double LN_2 = log(2);
69  
70    /**
71     * Returns {@code n!}, that is, the product of the first {@code n} positive
72     * integers, {@code 1} if {@code n == 0}, or {@code n!}, or
73     * {@link Double#POSITIVE_INFINITY} if {@code n! > Double.MAX_VALUE}.
74     *
75     * <p>The result is within 1 ulp of the true value.
76     *
77     * @throws IllegalArgumentException if {@code n < 0}
78     */
79    public static double factorial(int n) {
80      checkNonNegative("n", n);
81      if (n > MAX_FACTORIAL) {
82        return Double.POSITIVE_INFINITY;
83      } else {
84        // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate
85        // result than multiplying by everySixteenthFactorial[n >> 4] directly.
86        double accum = 1.0;
87        for (int i = 1 + (n & ~0xf); i <= n; i++) {
88          accum *= i;
89        }
90        return accum * everySixteenthFactorial[n >> 4];
91      }
92    }
93  
94    @VisibleForTesting
95    static final int MAX_FACTORIAL = 170;
96  
97    @VisibleForTesting
98    static final double[] everySixteenthFactorial = {
99        0x1.0p0,
100       0x1.30777758p44,
101       0x1.956ad0aae33a4p117,
102       0x1.ee69a78d72cb6p202,
103       0x1.fe478ee34844ap295,
104       0x1.c619094edabffp394,
105       0x1.3638dd7bd6347p498,
106       0x1.7cac197cfe503p605,
107       0x1.1e5dfc140e1e5p716,
108       0x1.8ce85fadb707ep829,
109       0x1.95d5f3d928edep945};
110 
111   /**
112    * Returns {@code true} if {@code a} and {@code b} are within {@code tolerance} of each other.
113    *
114    * <p>Technically speaking, this is equivalent to
115    * {@code Math.abs(a - b) <= tolerance || Double.valueOf(a).equals(Double.valueOf(b))}.
116    *
117    * <p>Notable special cases include:
118    * <ul>
119    * <li>All NaNs are fuzzily equal.
120    * <li>If {@code a == b}, then {@code a} and {@code b} are always fuzzily equal.
121    * <li>Positive and negative zero are always fuzzily equal.
122    * <li>If {@code tolerance} is zero, and neither {@code a} nor {@code b} is NaN, then
123    * {@code a} and {@code b} are fuzzily equal if and only if {@code a == b}.
124    * <li>With {@link Double#POSITIVE_INFINITY} tolerance, all non-NaN values are fuzzily equal.
125    * <li>With finite tolerance, {@code Double.POSITIVE_INFINITY} and {@code
126    * Double.NEGATIVE_INFINITY} are fuzzily equal only to themselves.
127    * </li>
128    *
129    * <p>This is reflexive and symmetric, but <em>not</em> transitive, so it is <em>not</em> an
130    * equivalence relation and <em>not</em> suitable for use in {@link Object#equals}
131    * implementations.
132    *
133    * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
134    * @since 13.0
135    */
136   public static boolean fuzzyEquals(double a, double b, double tolerance) {
137     MathPreconditions.checkNonNegative("tolerance", tolerance);
138     return
139           Math.copySign(a - b, 1.0) <= tolerance
140            // copySign(x, 1.0) is a branch-free version of abs(x), but with different NaN semantics
141           || (a == b) // needed to ensure that infinities equal themselves
142           || (Double.isNaN(a) && Double.isNaN(b));
143   }
144 
145   /**
146    * Compares {@code a} and {@code b} "fuzzily," with a tolerance for nearly-equal values.
147    *
148    * <p>This method is equivalent to
149    * {@code fuzzyEquals(a, b, tolerance) ? 0 : Double.compare(a, b)}. In particular, like
150    * {@link Double#compare(double, double)}, it treats all NaN values as equal and greater than all
151    * other values (including {@link Double#POSITIVE_INFINITY}).
152    *
153    * <p>This is <em>not</em> a total ordering and is <em>not</em> suitable for use in
154    * {@link Comparable#compareTo} implementations.  In particular, it is not transitive.
155    *
156    * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
157    * @since 13.0
158    */
159   public static int fuzzyCompare(double a, double b, double tolerance) {
160     if (fuzzyEquals(a, b, tolerance)) {
161       return 0;
162     } else if (a < b) {
163       return -1;
164     } else if (a > b) {
165       return 1;
166     } else {
167       return Booleans.compare(Double.isNaN(a), Double.isNaN(b));
168     }
169   }
170 
171   private DoubleMath() {}
172 }
173